package com.sheng.leetcode.year2023.month01.day26;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2023/01/31
 * <p>
 * 1663. 具有给定数值的最小字符串<p>
 * <p>
 * 小写字符 的 数值 是它在字母表中的位置（从 1 开始），因此 a 的数值为 1 ，b 的数值为 2 ，c 的数值为 3 ，以此类推。<p>
 * 字符串由若干小写字符组成，字符串的数值 为各字符的数值之和。例如，字符串 "abe" 的数值等于 1 + 2 + 5 = 8 。<p>
 * 给你两个整数 n 和 k 。返回 长度 等于 n 且 数值 等于 k 的 字典序最小 的字符串。<p>
 * 注意，如果字符串 x 在字典排序中位于 y 之前，就认为 x 字典序比 y 小，有以下两种情况：<p>
 * x 是 y 的一个前缀；<p>
 * 如果 i 是 x[i] != y[i] 的第一个位置，且 x[i] 在字母表中的位置比 y[i] 靠前。<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 3, k = 27<p>
 * 输出："aay"<p>
 * 解释：字符串的数值为 1 + 1 + 25 = 27，它是数值满足要求且长度等于 3 字典序最小的字符串。<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 5, k = 73<p>
 * 输出："aaszz"<p>
 * <p>
 * 提示：<p>
 * 1 <= n <= 10^5<p>
 * n <= k <= 26 * n<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/smallest-string-with-a-given-numeric-value">1663. 具有给定数值的最小字符串</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1663 {

    @Test
    public void test01() {
//        int n = 3, k = 27;
        int n = 5, k = 73;
        System.out.println(new Solution().getSmallestString(n, k));
    }
}

class Solution {
    public String getSmallestString(int n, int k) {
        char[] chars = new char[n];
        Arrays.fill(chars, 'a');
        int i = n - 1, d = k - n;
        for (; d > 25; d -= 25) {
            chars[i--] = 'z';
        }
        chars[i] = (char) ('a' + d);
        return String.valueOf(chars);
        // 暴力破解，超时
//        StringBuilder str = new StringBuilder();
//        for (int i = 0; i < n; i++) {
//            if (k > n - i + 25) {
//                // 直接拼接 z 即可
//                str = new StringBuilder("z").append(str);
//                k -= 26;
//            } else {
//                str = new StringBuilder(String.valueOf((char) (k - n + i + 'a'))).append(str);
//                i++;
//                while (i < n) {
//                    i++;
//                    str = new StringBuilder("a").append(str);
//                }
//            }
//        }
//        return str.toString();
    }
}
